/*
 * Copyright (C) 2009 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "dicttrie.h"
#include "dictbuilder.h"
#include "lpicache.h"
#include "mystdlib.h"
#include "ngram.h"
#include <QFile>
#include <QDebug>

namespace ime_pinyin
{

DictTrie::DictTrie()
{
    spl_trie_ = SpellingTrie::get_cpinstance();

    root_ = NULL;
    splid_le0_index_ = NULL;
    lma_node_num_le0_ = 0;
    nodes_ge1_ = NULL;
    lma_node_num_ge1_ = 0;
    lma_idx_buf_ = NULL;
    lma_idx_buf_len_ = 0;
    total_lma_num_ = 0;
    top_lmas_num_ = 0;
    dict_list_ = NULL;

    parsing_marks_ = NULL;
    mile_stones_ = NULL;
    reset_milestones(0, kFirstValidMileStoneHandle);
}

DictTrie::~DictTrie()
{
    free_resource(true);
}

void DictTrie::free_resource(bool free_dict_list)
{
    if (NULL != root_) {
        free(root_);
    }
    root_ = NULL;

    if (NULL != splid_le0_index_) {
        free(splid_le0_index_);
    }
    splid_le0_index_ = NULL;

    if (NULL != nodes_ge1_) {
        free(nodes_ge1_);
    }
    nodes_ge1_ = NULL;

    if (NULL != nodes_ge1_) {
        free(nodes_ge1_);
    }
    nodes_ge1_ = NULL;

    if (free_dict_list) {
        if (NULL != dict_list_) {
            delete dict_list_;
        }
        dict_list_ = NULL;
    }

    if (parsing_marks_) {
        delete [] parsing_marks_;
    }
    parsing_marks_ = NULL;

    if (mile_stones_) {
        delete [] mile_stones_;
    }
    mile_stones_ = NULL;

    reset_milestones(0, kFirstValidMileStoneHandle);
}

inline size_t DictTrie::get_son_offset(const LmaNodeGE1 *node)
{
    return ((size_t)node->son_1st_off_l + ((size_t)node->son_1st_off_h << 16));
}

inline size_t DictTrie::get_homo_idx_buf_offset(const LmaNodeGE1 *node)
{
    return ((size_t)node->homo_idx_buf_off_l +
            ((size_t)node->homo_idx_buf_off_h << 16));
}

inline LemmaIdType DictTrie::get_lemma_id(size_t id_offset)
{
    LemmaIdType id = 0;
    for (uint16 pos = kLemmaIdSize - 1; pos > 0; pos--) {
        id = (id << 8) + lma_idx_buf_[id_offset * kLemmaIdSize + pos];
    }
    id = (id << 8) + lma_idx_buf_[id_offset * kLemmaIdSize];
    return id;
}

#ifdef ___BUILD_MODEL___
bool DictTrie::build_dict(const char *fn_raw, const char *fn_validhzs)
{
    DictBuilder *dict_builder = new DictBuilder();

    free_resource(true);

    return dict_builder->build_dict(fn_raw, fn_validhzs, this);
}

bool DictTrie::save_dict(FILE *fp)
{
    if (NULL == fp) {
        return false;
    }

    if (fwrite(&lma_node_num_le0_, sizeof(size_t), 1, fp) != 1) {
        return false;
    }

    if (fwrite(&lma_node_num_ge1_, sizeof(size_t), 1, fp) != 1) {
        return false;
    }

    if (fwrite(&lma_idx_buf_len_, sizeof(size_t), 1, fp) != 1) {
        return false;
    }

    if (fwrite(&top_lmas_num_, sizeof(size_t), 1, fp) != 1) {
        return false;
    }

    if (fwrite(root_, sizeof(LmaNodeLE0), lma_node_num_le0_, fp)
            != lma_node_num_le0_) {
        return false;
    }

    if (fwrite(nodes_ge1_, sizeof(LmaNodeGE1), lma_node_num_ge1_, fp)
            != lma_node_num_ge1_) {
        return false;
    }

    if (fwrite(lma_idx_buf_, sizeof(unsigned char), lma_idx_buf_len_, fp) !=
            lma_idx_buf_len_) {
        return false;
    }

    return true;
}

bool DictTrie::save_dict(const char *filename)
{
    if (NULL == filename) {
        return false;
    }

    if (NULL == root_ || NULL == dict_list_) {
        return false;
    }

    SpellingTrie &spl_trie = SpellingTrie::get_instance();
    NGram &ngram = NGram::get_instance();

    FILE *fp = fopen(filename, "wb");
    if (NULL == fp) {
        return false;
    }

    if (!spl_trie.save_spl_trie(fp) || !dict_list_->save_list(fp) ||
            !save_dict(fp) || !ngram.save_ngram(fp)) {
        fclose(fp);
        return false;
    }

    fclose(fp);
    return true;
}
#endif  // ___BUILD_MODEL___

bool DictTrie::load_dict(QFile &fp)
{
    qDebug()<<"load_dict";
//    if (NULL == fp) {
//        return false;
//    }

//    if (fread(&lma_node_num_le0_, sizeof(size_t), 1, fp) != 1) {
//        return false;
//    }

//    if (fread(&lma_node_num_ge1_, sizeof(size_t), 1, fp) != 1) {
//        return false;
//    }

//    if (fread(&lma_idx_buf_len_, sizeof(size_t), 1, fp) != 1) {
//        return false;
//    }

//    if (fread(&top_lmas_num_, sizeof(size_t), 1, fp) != 1 ||
//            top_lmas_num_ >= lma_idx_buf_len_) {
//        return false;
//    }
    if (!fp.isOpen()){

        return false;
    }
    qint64 size = sizeof(size_t);
    qDebug()<<"size : " <<size;
    qDebug()<<" pos0 : " << fp.pos();
    if (fp.read((char*)&lma_node_num_le0_, size) != size){
        qDebug()<<"11" ;
        return false;
    }
    qDebug()<<" pos1 : " << fp.pos();
    if (fp.read((char*)&lma_node_num_ge1_, size) != size){
        qDebug()<<"22";
        return false;
    }
      qDebug()<<" pos2 : " << fp.pos();
    if (fp.read((char*)&lma_idx_buf_len_, size) != size){
        qDebug()<<"33";
        return false;
    }
      qDebug()<<" pos3 : " << fp.pos();
    qDebug()<<"--  "<< lma_node_num_le0_ << lma_node_num_ge1_ << lma_idx_buf_len_;
    if ((fp.read((char*)&top_lmas_num_, size) != size) || (top_lmas_num_ >= lma_idx_buf_len_)){
        qDebug()<<"44" << top_lmas_num_ << lma_idx_buf_len_;
        return false;
    }
    free_resource(false);

    root_ = static_cast<LmaNodeLE0 *>
            (malloc(lma_node_num_le0_ * sizeof(LmaNodeLE0)));
    nodes_ge1_ = static_cast<LmaNodeGE1 *>
            (malloc(lma_node_num_ge1_ * sizeof(LmaNodeGE1)));
    lma_idx_buf_ = (unsigned char *)malloc(lma_idx_buf_len_);
    total_lma_num_ = lma_idx_buf_len_ / kLemmaIdSize;

    size_t buf_size = SpellingTrie::get_instance().get_spelling_num() + 1;
    assert(lma_node_num_le0_ <= buf_size);
    splid_le0_index_ = static_cast<uint16 *>(malloc(buf_size * sizeof(uint16)));

    // Init the space for parsing.
    parsing_marks_ = new ParsingMark[kMaxParsingMark];
    mile_stones_ = new MileStone[kMaxMileStone];
    reset_milestones(0, kFirstValidMileStoneHandle);

    if (NULL == root_ || NULL == nodes_ge1_ || NULL == lma_idx_buf_ ||
            NULL == splid_le0_index_ || NULL == parsing_marks_ ||
            NULL == mile_stones_) {
        free_resource(false);
        qDebug()<<"1";
        return false;
    }

//    if (fread(root_, sizeof(LmaNodeLE0), lma_node_num_le0_, fp)
//            != lma_node_num_le0_) {
//        return false;
//    }

//    if (fread(nodes_ge1_, sizeof(LmaNodeGE1), lma_node_num_ge1_, fp)
//            != lma_node_num_ge1_) {
//        return false;
//    }

//    if (fread(lma_idx_buf_, sizeof(unsigned char), lma_idx_buf_len_, fp) !=
//            lma_idx_buf_len_) {
//        return false;
//    }

    size = sizeof(LmaNodeLE0) * lma_node_num_le0_;
    if (fp.read((char*)root_, size) != size){
        qDebug()<<"2";
        return false;
    }
    size = sizeof(LmaNodeGE1) * lma_node_num_ge1_;
    if (fp.read((char*)nodes_ge1_, size) != size){
        qDebug()<<"3";
        return false;
    }
    size = sizeof(unsigned char) * lma_idx_buf_len_;
    if (fp.read((char*)lma_idx_buf_, size) != size){
    qDebug()<<"4";
        return false;
    }

    // The quick index for the first level sons
    uint16 last_splid = kFullSplIdStart;
    size_t last_pos = 0;
    for (size_t i = 1; i < lma_node_num_le0_; i++) {
        for (uint16 splid = last_splid; splid < root_[i].spl_idx; splid++) {
            splid_le0_index_[splid - kFullSplIdStart] = last_pos;
        }

        splid_le0_index_[root_[i].spl_idx - kFullSplIdStart] =
                static_cast<uint16>(i);
        last_splid = root_[i].spl_idx;
        last_pos = i;
    }

    for (uint16 splid = last_splid + 1;
         splid < buf_size + kFullSplIdStart; splid++) {
        assert(static_cast<size_t>(splid - kFullSplIdStart) < buf_size);
        splid_le0_index_[splid - kFullSplIdStart] = last_pos + 1;
    }
    qDebug()<<"load_dict ok";
    return true;
}

//bool DictTrie::load_dict(const char *filename, LemmaIdType start_id,
//                         LemmaIdType end_id)
bool DictTrie::load_dict(QString &filename, LemmaIdType start_id,
                         LemmaIdType end_id)
{
    if (NULL == filename || end_id <= start_id) {
        return false;
    }
    QFile myFile(filename);
    if (!myFile.open(QIODevice::ReadOnly )){
        qDebug()<<"open myfile false " << filename;
        return false;
    }
    qDebug()<<"DictTrie load_dict : " << myFile.handle();

    free_resource(true);

    dict_list_ = new DictList();
    if (NULL == dict_list_) {
        qDebug()<<"null"; qDebug()<<"-------11" << total_lma_num_ << end_id - start_id + 1;
        myFile.close();
        return false;
    }

    SpellingTrie &spl_trie = SpellingTrie::get_instance();
    NGram &ngram = NGram::get_instance();

    if (!spl_trie.load_spl_trie(myFile) || !dict_list_->load_list(myFile) ||
            !load_dict(myFile) || !ngram.load_ngram(myFile) ||
            total_lma_num_ > end_id - start_id + 1) {
        qDebug()<<"-------11" << total_lma_num_ << end_id - start_id + 1;
        free_resource(true);
        myFile.close();
        return false;
    }
 qDebug()<<"-------111" << total_lma_num_ << end_id - start_id + 1 << myFile.pos();
    myFile.close();
    return true;
}

//bool DictTrie::load_dict_fd(int sys_fd, long start_offset,
//                            long length, LemmaIdType start_id,
//                            LemmaIdType end_id)
//{
//    if (start_offset < 0 || length <= 0 || end_id <= start_id) {
//        return false;
//    }

//    FILE *fp = fdopen(sys_fd, "rb");
//    if (NULL == fp) {
//        return false;
//    }

//    if (-1 == fseek(fp, start_offset, SEEK_SET)) {
//        fclose(fp);
//        return false;
//    }

//    free_resource(true);

//    dict_list_ = new DictList();
//    if (NULL == dict_list_) {
//        fclose(fp);
//        return false;
//    }

//    SpellingTrie &spl_trie = SpellingTrie::get_instance();
//    NGram &ngram = NGram::get_instance();

//    if (!spl_trie.load_spl_trie(fp) || !dict_list_->load_list(fp) ||
//            !load_dict(fp) || !ngram.load_ngram(fp) ||
//            ftell(fp) < start_offset + length ||
//            total_lma_num_ > end_id - start_id + 1) {
//        free_resource(true);
//        fclose(fp);
//        return false;
//    }

//    fclose(fp);
//    return true;
//}

size_t DictTrie::fill_lpi_buffer(LmaPsbItem lpi_items[], size_t lpi_max,
                                 LmaNodeLE0 *node)
{
    size_t lpi_num = 0;
    NGram &ngram = NGram::get_instance();
    for (size_t homo = 0; homo < (size_t)node->num_of_homo; homo++) {
        lpi_items[lpi_num].id = get_lemma_id(node->homo_idx_buf_off +
                                             homo);
        lpi_items[lpi_num].lma_len = 1;
        lpi_items[lpi_num].psb =
                static_cast<LmaScoreType>(ngram.get_uni_psb(lpi_items[lpi_num].id));
        lpi_num++;
        if (lpi_num >= lpi_max) {
            break;
        }
    }

    return lpi_num;
}

size_t DictTrie::fill_lpi_buffer(LmaPsbItem lpi_items[], size_t lpi_max,
                                 size_t homo_buf_off, LmaNodeGE1 *node,
                                 uint16 lma_len)
{
    size_t lpi_num = 0;
    NGram &ngram = NGram::get_instance();
    for (size_t homo = 0; homo < (size_t)node->num_of_homo; homo++) {
        lpi_items[lpi_num].id = get_lemma_id(homo_buf_off + homo);
        lpi_items[lpi_num].lma_len = lma_len;
        lpi_items[lpi_num].psb =
                static_cast<LmaScoreType>(ngram.get_uni_psb(lpi_items[lpi_num].id));
        lpi_num++;
        if (lpi_num >= lpi_max) {
            break;
        }
    }

    return lpi_num;
}

void DictTrie::reset_milestones(uint16 from_step, MileStoneHandle from_handle)
{
    if (0 == from_step) {
        parsing_marks_pos_ = 0;
        mile_stones_pos_ = kFirstValidMileStoneHandle;
    } else {
        if (from_handle > 0 && from_handle < mile_stones_pos_) {
            mile_stones_pos_ = from_handle;

            MileStone *mile_stone = mile_stones_ + from_handle;
            parsing_marks_pos_ = mile_stone->mark_start;
        }
    }
}

MileStoneHandle DictTrie::extend_dict(MileStoneHandle from_handle,
                                      const DictExtPara *dep,
                                      LmaPsbItem *lpi_items, size_t lpi_max,
                                      size_t *lpi_num)
{
    if (NULL == dep) {
        return 0;
    }

    // from LmaNodeLE0 (root) to LmaNodeLE0
    if (0 == from_handle) {
        assert(0 == dep->splids_extended);
        return extend_dict0(from_handle, dep, lpi_items, lpi_max, lpi_num);
    }

    // from LmaNodeLE0 to LmaNodeGE1
    if (1 == dep->splids_extended) {
        return extend_dict1(from_handle, dep, lpi_items, lpi_max, lpi_num);
    }

    // From LmaNodeGE1 to LmaNodeGE1
    return extend_dict2(from_handle, dep, lpi_items, lpi_max, lpi_num);
}

MileStoneHandle DictTrie::extend_dict0(MileStoneHandle from_handle,
                                       const DictExtPara *dep,
                                       LmaPsbItem *lpi_items,
                                       size_t lpi_max, size_t *lpi_num)
{
    assert(NULL != dep && 0 == from_handle);
    *lpi_num = 0;
    MileStoneHandle ret_handle = 0;

    uint16 splid = dep->splids[dep->splids_extended];
    uint16 id_start = dep->id_start;
    uint16 id_num = dep->id_num;

    LpiCache &lpi_cache = LpiCache::get_instance();
    bool cached = lpi_cache.is_cached(splid);

    // 2. Begin exgtending
    // 2.1 Get the LmaPsbItem list
    LmaNodeLE0 *node = root_;
    size_t son_start = splid_le0_index_[id_start - kFullSplIdStart];
    size_t son_end = splid_le0_index_[id_start + id_num - kFullSplIdStart];
    for (size_t son_pos = son_start; son_pos < son_end; son_pos++) {
        assert(1 == node->son_1st_off);
        LmaNodeLE0 *son = root_ + son_pos;
        assert(son->spl_idx >= id_start && son->spl_idx < id_start + id_num);

        if (!cached && *lpi_num < lpi_max) {
            bool need_lpi = true;
            if (spl_trie_->is_half_id_yunmu(splid) && son_pos != son_start) {
                need_lpi = false;
            }

            if (need_lpi)
                *lpi_num += fill_lpi_buffer(lpi_items + (*lpi_num),
                                            lpi_max - *lpi_num, son);
        }

        // If necessary, fill in a new mile stone.
        if (son->spl_idx == id_start) {
            if (mile_stones_pos_ < kMaxMileStone &&
                    parsing_marks_pos_ < kMaxParsingMark) {
                parsing_marks_[parsing_marks_pos_].node_offset = son_pos;
                parsing_marks_[parsing_marks_pos_].node_num = id_num;
                mile_stones_[mile_stones_pos_].mark_start = parsing_marks_pos_;
                mile_stones_[mile_stones_pos_].mark_num = 1;
                ret_handle = mile_stones_pos_;
                parsing_marks_pos_++;
                mile_stones_pos_++;
            }
        }

        if (son->spl_idx >= id_start + id_num - 1) {
            break;
        }
    }

    //  printf("----- parsing marks: %d, mile stone: %d \n", parsing_marks_pos_,
    //      mile_stones_pos_);
    return ret_handle;
}

MileStoneHandle DictTrie::extend_dict1(MileStoneHandle from_handle,
                                       const DictExtPara *dep,
                                       LmaPsbItem *lpi_items,
                                       size_t lpi_max, size_t *lpi_num)
{
    assert(NULL != dep && from_handle > 0 && from_handle < mile_stones_pos_);

    MileStoneHandle ret_handle = 0;

    // 1. If this is a half Id, get its corresponding full starting Id and
    // number of full Id.
    size_t ret_val = 0;

    uint16 id_start = dep->id_start;
    uint16 id_num = dep->id_num;

    // 2. Begin extending.
    MileStone *mile_stone = mile_stones_ + from_handle;

    for (uint16 h_pos = 0; h_pos < mile_stone->mark_num; h_pos++) {
        ParsingMark p_mark = parsing_marks_[mile_stone->mark_start + h_pos];
        uint16 ext_num = p_mark.node_num;
        for (uint16 ext_pos = 0; ext_pos < ext_num; ext_pos++) {
            LmaNodeLE0 *node = root_ + p_mark.node_offset + ext_pos;
            size_t found_start = 0;
            size_t found_num = 0;
            for (size_t son_pos = 0; son_pos < (size_t)node->num_of_son; son_pos++) {
                assert(node->son_1st_off <= lma_node_num_ge1_);
                LmaNodeGE1 *son = nodes_ge1_ + node->son_1st_off + son_pos;
                if (son->spl_idx >= id_start
                        && son->spl_idx < id_start + id_num) {
                    if (*lpi_num < lpi_max) {
                        size_t homo_buf_off = get_homo_idx_buf_offset(son);
                        *lpi_num += fill_lpi_buffer(lpi_items + (*lpi_num),
                                                    lpi_max - *lpi_num, homo_buf_off, son,
                                                    2);
                    }

                    // If necessary, fill in the new DTMI
                    if (0 == found_num) {
                        found_start = son_pos;
                    }
                    found_num++;
                }
                if (son->spl_idx >= id_start + id_num - 1 || son_pos ==
                        (size_t)node->num_of_son - 1) {
                    if (found_num > 0) {
                        if (mile_stones_pos_ < kMaxMileStone &&
                                parsing_marks_pos_ < kMaxParsingMark) {
                            parsing_marks_[parsing_marks_pos_].node_offset =
                                    node->son_1st_off + found_start;
                            parsing_marks_[parsing_marks_pos_].node_num = found_num;
                            if (0 == ret_val)
                                mile_stones_[mile_stones_pos_].mark_start =
                                        parsing_marks_pos_;
                            parsing_marks_pos_++;
                        }

                        ret_val++;
                    }
                    break;
                }  // for son_pos
            }  // for ext_pos
        }  // for h_pos
    }

    if (ret_val > 0) {
        mile_stones_[mile_stones_pos_].mark_num = ret_val;
        ret_handle = mile_stones_pos_;
        mile_stones_pos_++;
        ret_val = 1;
    }

    //  printf("----- parsing marks: %d, mile stone: %d \n", parsing_marks_pos_,
    //         mile_stones_pos_);
    return ret_handle;
}

MileStoneHandle DictTrie::extend_dict2(MileStoneHandle from_handle,
                                       const DictExtPara *dep,
                                       LmaPsbItem *lpi_items,
                                       size_t lpi_max, size_t *lpi_num)
{
    assert(NULL != dep && from_handle > 0 && from_handle < mile_stones_pos_);

    MileStoneHandle ret_handle = 0;

    // 1. If this is a half Id, get its corresponding full starting Id and
    // number of full Id.
    size_t ret_val = 0;

    uint16 id_start = dep->id_start;
    uint16 id_num = dep->id_num;

    // 2. Begin extending.
    MileStone *mile_stone = mile_stones_ + from_handle;

    for (uint16 h_pos = 0; h_pos < mile_stone->mark_num; h_pos++) {
        ParsingMark p_mark = parsing_marks_[mile_stone->mark_start + h_pos];
        uint16 ext_num = p_mark.node_num;
        for (uint16 ext_pos = 0; ext_pos < ext_num; ext_pos++) {
            LmaNodeGE1 *node = nodes_ge1_ + p_mark.node_offset + ext_pos;
            size_t found_start = 0;
            size_t found_num = 0;

            for (size_t son_pos = 0; son_pos < (size_t)node->num_of_son; son_pos++) {
                assert(node->son_1st_off_l > 0 || node->son_1st_off_h > 0);
                LmaNodeGE1 *son = nodes_ge1_ + get_son_offset(node) + son_pos;
                if (son->spl_idx >= id_start
                        && son->spl_idx < id_start + id_num) {
                    if (*lpi_num < lpi_max) {
                        size_t homo_buf_off = get_homo_idx_buf_offset(son);
                        *lpi_num += fill_lpi_buffer(lpi_items + (*lpi_num),
                                                    lpi_max - *lpi_num, homo_buf_off, son,
                                                    dep->splids_extended + 1);
                    }

                    // If necessary, fill in the new DTMI
                    if (0 == found_num) {
                        found_start = son_pos;
                    }
                    found_num++;
                }
                if (son->spl_idx >= id_start + id_num - 1 || son_pos ==
                        (size_t)node->num_of_son - 1) {
                    if (found_num > 0) {
                        if (mile_stones_pos_ < kMaxMileStone &&
                                parsing_marks_pos_ < kMaxParsingMark) {
                            parsing_marks_[parsing_marks_pos_].node_offset =
                                    get_son_offset(node) + found_start;
                            parsing_marks_[parsing_marks_pos_].node_num = found_num;
                            if (0 == ret_val)
                                mile_stones_[mile_stones_pos_].mark_start =
                                        parsing_marks_pos_;
                            parsing_marks_pos_++;
                        }

                        ret_val++;
                    }
                    break;
                }
            }  // for son_pos
        }  // for ext_pos
    }  // for h_pos

    if (ret_val > 0) {
        mile_stones_[mile_stones_pos_].mark_num = ret_val;
        ret_handle = mile_stones_pos_;
        mile_stones_pos_++;
    }

    // printf("----- parsing marks: %d, mile stone: %d \n", parsing_marks_pos_,
    //        mile_stones_pos_);
    return ret_handle;
}

bool DictTrie::try_extend(const uint16 *splids, uint16 splid_num,
                          LemmaIdType id_lemma)
{
    if (0 == splid_num || NULL == splids) {
        return false;
    }

    void *node = root_ + splid_le0_index_[splids[0] - kFullSplIdStart];

    for (uint16 pos = 1; pos < splid_num; pos++) {
        if (1 == pos) {
            LmaNodeLE0 *node_le0 = reinterpret_cast<LmaNodeLE0 *>(node);
            LmaNodeGE1 *node_son;
            uint16 son_pos;
            for (son_pos = 0; son_pos < static_cast<uint16>(node_le0->num_of_son);
                 son_pos++) {
                assert(node_le0->son_1st_off <= lma_node_num_ge1_);
                node_son = nodes_ge1_ + node_le0->son_1st_off
                        + son_pos;
                if (node_son->spl_idx == splids[pos]) {
                    break;
                }
            }
            if (son_pos < node_le0->num_of_son) {
                node = reinterpret_cast<void *>(node_son);
            } else {
                return false;
            }
        } else {
            LmaNodeGE1 *node_ge1 = reinterpret_cast<LmaNodeGE1 *>(node);
            LmaNodeGE1 *node_son;
            uint16 son_pos;
            for (son_pos = 0; son_pos < static_cast<uint16>(node_ge1->num_of_son);
                 son_pos++) {
                assert(node_ge1->son_1st_off_l > 0 || node_ge1->son_1st_off_h > 0);
                node_son = nodes_ge1_ + get_son_offset(node_ge1) + son_pos;
                if (node_son->spl_idx == splids[pos]) {
                    break;
                }
            }
            if (son_pos < node_ge1->num_of_son) {
                node = reinterpret_cast<void *>(node_son);
            } else {
                return false;
            }
        }
    }

    if (1 == splid_num) {
        LmaNodeLE0 *node_le0 = reinterpret_cast<LmaNodeLE0 *>(node);
        size_t num_of_homo = (size_t)node_le0->num_of_homo;
        for (size_t homo_pos = 0; homo_pos < num_of_homo; homo_pos++) {
            LemmaIdType id_this = get_lemma_id(node_le0->homo_idx_buf_off + homo_pos);
            char16 str[2];
            get_lemma_str(id_this, str, 2);
            if (id_this == id_lemma) {
                return true;
            }
        }
    } else {
        LmaNodeGE1 *node_ge1 = reinterpret_cast<LmaNodeGE1 *>(node);
        size_t num_of_homo = (size_t)node_ge1->num_of_homo;
        for (size_t homo_pos = 0; homo_pos < num_of_homo; homo_pos++) {
            size_t node_homo_off = get_homo_idx_buf_offset(node_ge1);
            if (get_lemma_id(node_homo_off + homo_pos) == id_lemma) {
                return true;
            }
        }
    }

    return false;
}

size_t DictTrie::get_lpis(const uint16 *splid_str, uint16 splid_str_len,
                          LmaPsbItem *lma_buf, size_t max_lma_buf)
{
    if (splid_str_len > kMaxLemmaSize) {
        return 0;
    }

#define MAX_EXTENDBUF_LEN 200

    size_t *node_buf1[MAX_EXTENDBUF_LEN];  // use size_t for data alignment
    size_t *node_buf2[MAX_EXTENDBUF_LEN];
    LmaNodeLE0 **node_fr_le0 =
            reinterpret_cast<LmaNodeLE0 **>(node_buf1);     // Nodes from.
    LmaNodeLE0 **node_to_le0 =
            reinterpret_cast<LmaNodeLE0 **>(node_buf2);     // Nodes to.
    LmaNodeGE1 **node_fr_ge1 = NULL;
    LmaNodeGE1 **node_to_ge1 = NULL;
    size_t node_fr_num = 1;
    size_t node_to_num = 0;
    node_fr_le0[0] = root_;
    if (NULL == node_fr_le0[0]) {
        return 0;
    }

    size_t spl_pos = 0;

    while (spl_pos < splid_str_len) {
        uint16 id_num = 1;
        uint16 id_start = splid_str[spl_pos];
        // If it is a half id
        if (spl_trie_->is_half_id(splid_str[spl_pos])) {
            id_num = spl_trie_->half_to_full(splid_str[spl_pos], &id_start);
            assert(id_num > 0);
        }

        // Extend the nodes
        if (0 == spl_pos) {  // From LmaNodeLE0 (root) to LmaNodeLE0 nodes
            for (size_t node_fr_pos = 0; node_fr_pos < node_fr_num; node_fr_pos++) {
                LmaNodeLE0 *node = node_fr_le0[node_fr_pos];
                assert(node == root_ && 1 == node_fr_num);
                size_t son_start = splid_le0_index_[id_start - kFullSplIdStart];
                size_t son_end =
                        splid_le0_index_[id_start + id_num - kFullSplIdStart];
                for (size_t son_pos = son_start; son_pos < son_end; son_pos++) {
                    assert(1 == node->son_1st_off);
                    LmaNodeLE0 *node_son = root_ + son_pos;
                    assert(node_son->spl_idx >= id_start
                           && node_son->spl_idx < id_start + id_num);
                    if (node_to_num < MAX_EXTENDBUF_LEN) {
                        node_to_le0[node_to_num] = node_son;
                        node_to_num++;
                    }
                    // id_start + id_num - 1 is the last one, which has just been
                    // recorded.
                    if (node_son->spl_idx >= id_start + id_num - 1) {
                        break;
                    }
                }
            }

            spl_pos++;
            if (spl_pos >= splid_str_len || node_to_num == 0) {
                break;
            }
            // Prepare the nodes for next extending
            // next time, from LmaNodeLE0 to LmaNodeGE1
            LmaNodeLE0 **node_tmp = node_fr_le0;
            node_fr_le0 = node_to_le0;
            node_to_le0 = NULL;
            node_to_ge1 = reinterpret_cast<LmaNodeGE1 **>(node_tmp);
        } else if (1 == spl_pos) {  // From LmaNodeLE0 to LmaNodeGE1 nodes
            for (size_t node_fr_pos = 0; node_fr_pos < node_fr_num; node_fr_pos++) {
                LmaNodeLE0 *node = node_fr_le0[node_fr_pos];
                for (size_t son_pos = 0; son_pos < (size_t)node->num_of_son;
                     son_pos++) {
                    assert(node->son_1st_off <= lma_node_num_ge1_);
                    LmaNodeGE1 *node_son = nodes_ge1_ + node->son_1st_off
                            + son_pos;
                    if (node_son->spl_idx >= id_start
                            && node_son->spl_idx < id_start + id_num) {
                        if (node_to_num < MAX_EXTENDBUF_LEN) {
                            node_to_ge1[node_to_num] = node_son;
                            node_to_num++;
                        }
                    }
                    // id_start + id_num - 1 is the last one, which has just been
                    // recorded.
                    if (node_son->spl_idx >= id_start + id_num - 1) {
                        break;
                    }
                }
            }

            spl_pos++;
            if (spl_pos >= splid_str_len || node_to_num == 0) {
                break;
            }
            // Prepare the nodes for next extending
            // next time, from LmaNodeGE1 to LmaNodeGE1
            node_fr_ge1 = node_to_ge1;
            node_to_ge1 = reinterpret_cast<LmaNodeGE1 **>(node_fr_le0);
            node_fr_le0 = NULL;
            node_to_le0 = NULL;
        } else {  // From LmaNodeGE1 to LmaNodeGE1 nodes
            for (size_t node_fr_pos = 0; node_fr_pos < node_fr_num; node_fr_pos++) {
                LmaNodeGE1 *node = node_fr_ge1[node_fr_pos];
                for (size_t son_pos = 0; son_pos < (size_t)node->num_of_son;
                     son_pos++) {
                    assert(node->son_1st_off_l > 0 || node->son_1st_off_h > 0);
                    LmaNodeGE1 *node_son = nodes_ge1_
                            + get_son_offset(node) + son_pos;
                    if (node_son->spl_idx >= id_start
                            && node_son->spl_idx < id_start + id_num) {
                        if (node_to_num < MAX_EXTENDBUF_LEN) {
                            node_to_ge1[node_to_num] = node_son;
                            node_to_num++;
                        }
                    }
                    // id_start + id_num - 1 is the last one, which has just been
                    // recorded.
                    if (node_son->spl_idx >= id_start + id_num - 1) {
                        break;
                    }
                }
            }

            spl_pos++;
            if (spl_pos >= splid_str_len || node_to_num == 0) {
                break;
            }
            // Prepare the nodes for next extending
            // next time, from LmaNodeGE1 to LmaNodeGE1
            LmaNodeGE1 **node_tmp = node_fr_ge1;
            node_fr_ge1 = node_to_ge1;
            node_to_ge1 = node_tmp;
        }

        // The number of node for next extending
        node_fr_num = node_to_num;
        node_to_num = 0;
    }  // while

    if (0 == node_to_num) {
        return 0;
    }

    NGram &ngram = NGram::get_instance();
    size_t lma_num = 0;

    // If the length is 1, and the splid is a one-char Yunmu like 'a', 'o', 'e',
    // only those candidates for the full matched one-char id will be returned.
    if (1 == splid_str_len && spl_trie_->is_half_id_yunmu(splid_str[0])) {
        node_to_num = node_to_num > 0 ? 1 : 0;
    }

    for (size_t node_pos = 0; node_pos < node_to_num; node_pos++) {
        size_t num_of_homo = 0;
        if (spl_pos <= 1) {  // Get from LmaNodeLE0 nodes
            LmaNodeLE0 *node_le0 = node_to_le0[node_pos];
            num_of_homo = (size_t)node_le0->num_of_homo;
            for (size_t homo_pos = 0; homo_pos < num_of_homo; homo_pos++) {
                size_t ch_pos = lma_num + homo_pos;
                lma_buf[ch_pos].id =
                        get_lemma_id(node_le0->homo_idx_buf_off + homo_pos);
                lma_buf[ch_pos].lma_len = 1;
                lma_buf[ch_pos].psb =
                        static_cast<LmaScoreType>(ngram.get_uni_psb(lma_buf[ch_pos].id));

                if (lma_num + homo_pos >= max_lma_buf - 1) {
                    break;
                }
            }
        } else {  // Get from LmaNodeGE1 nodes
            LmaNodeGE1 *node_ge1 = node_to_ge1[node_pos];
            num_of_homo = (size_t)node_ge1->num_of_homo;
            for (size_t homo_pos = 0; homo_pos < num_of_homo; homo_pos++) {
                size_t ch_pos = lma_num + homo_pos;
                size_t node_homo_off = get_homo_idx_buf_offset(node_ge1);
                lma_buf[ch_pos].id = get_lemma_id(node_homo_off + homo_pos);
                lma_buf[ch_pos].lma_len = splid_str_len;
                lma_buf[ch_pos].psb =
                        static_cast<LmaScoreType>(ngram.get_uni_psb(lma_buf[ch_pos].id));

                if (ch_pos >= max_lma_buf - 1) {
                    break;
                }
            }
        }

        lma_num += num_of_homo;
        if (lma_num >= max_lma_buf) {
            lma_num = max_lma_buf;
            break;
        }
    }
    return lma_num;
}

uint16 DictTrie::get_lemma_str(LemmaIdType id_lemma, char16 *str_buf,
                               uint16 str_max)
{
    return dict_list_->get_lemma_str(id_lemma, str_buf, str_max);
}

uint16 DictTrie::get_lemma_splids(LemmaIdType id_lemma, uint16 *splids,
                                  uint16 splids_max, bool arg_valid)
{
    char16 lma_str[kMaxLemmaSize + 1];
    uint16 lma_len = get_lemma_str(id_lemma, lma_str, kMaxLemmaSize + 1);
    assert((!arg_valid && splids_max >= lma_len) || lma_len == splids_max);

    uint16 spl_mtrx[kMaxLemmaSize * 5];
    uint16 spl_start[kMaxLemmaSize + 1];
    spl_start[0] = 0;
    uint16 try_num = 1;

    for (uint16 pos = 0; pos < lma_len; pos++) {
        uint16 cand_splids_this = 0;
        if (arg_valid && spl_trie_->is_full_id(splids[pos])) {
            spl_mtrx[spl_start[pos]] = splids[pos];
            cand_splids_this = 1;
        } else {
            cand_splids_this = dict_list_->get_splids_for_hanzi(lma_str[pos],
                                                                arg_valid ? splids[pos] : 0, spl_mtrx + spl_start[pos],
                                                                kMaxLemmaSize * 5 - spl_start[pos]);
            assert(cand_splids_this > 0);
        }
        spl_start[pos + 1] = spl_start[pos] + cand_splids_this;
        try_num *= cand_splids_this;
    }

    for (uint16 try_pos = 0; try_pos < try_num; try_pos++) {
        uint16 mod = 1;
        for (uint16 pos = 0; pos < lma_len; pos++) {
            uint16 radix = spl_start[pos + 1] - spl_start[pos];
            splids[pos] = spl_mtrx[ spl_start[pos] + try_pos / mod % radix];
            mod *= radix;
        }

        if (try_extend(splids, lma_len, id_lemma)) {
            return lma_len;
        }
    }

    return 0;
}

void DictTrie::set_total_lemma_count_of_others(size_t count)
{
    NGram &ngram = NGram::get_instance();
    ngram.set_total_freq_none_sys(count);
}

void DictTrie::convert_to_hanzis(char16 *str, uint16 str_len)
{
    return dict_list_->convert_to_hanzis(str, str_len);
}

void DictTrie::convert_to_scis_ids(char16 *str, uint16 str_len)
{
    return dict_list_->convert_to_scis_ids(str, str_len);
}

LemmaIdType DictTrie::get_lemma_id(const char16 lemma_str[], uint16 lemma_len)
{
    if (NULL == lemma_str || lemma_len > kMaxLemmaSize) {
        return 0;
    }

    return dict_list_->get_lemma_id(lemma_str, lemma_len);
}

size_t DictTrie::predict_top_lmas(size_t his_len, NPredictItem *npre_items,
                                  size_t npre_max, size_t b4_used)
{
    NGram &ngram = NGram::get_instance();

    size_t item_num = 0;
    size_t top_lmas_id_offset = lma_idx_buf_len_ / kLemmaIdSize - top_lmas_num_;
    size_t top_lmas_pos = 0;
    while (item_num < npre_max && top_lmas_pos < top_lmas_num_) {
        memset(npre_items + item_num, 0, sizeof(NPredictItem));
        LemmaIdType top_lma_id = get_lemma_id(top_lmas_id_offset + top_lmas_pos);
        top_lmas_pos += 1;
        if (dict_list_->get_lemma_str(top_lma_id,
                                      npre_items[item_num].pre_hzs,
                                      kMaxLemmaSize - 1) == 0) {
            continue;
        }
        npre_items[item_num].psb = ngram.get_uni_psb(top_lma_id);
        npre_items[item_num].his_len = his_len;
        item_num++;
    }
    return item_num;
}

size_t DictTrie::predict(const char16 *last_hzs, uint16 hzs_len,
                         NPredictItem *npre_items, size_t npre_max,
                         size_t b4_used)
{
    return dict_list_->predict(last_hzs, hzs_len, npre_items, npre_max, b4_used);
}
}  // namespace ime_pinyin
